package test.day07;

public class BinaryTreeMaximumPathSum {
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {}
		TreeNode(int val) { this.val = val; }
		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	int max = Integer.MIN_VALUE;

	int help(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = help(root.left);
		int right = help(root.right);
		max = Math.max(max, left + right + root.val);
		int res = left > right ? left + root.val : right + root.val;
		return res > 0 ? res : 0;
	}

	public int maxPathSum(TreeNode root) {
		help(root);
		return max;
	}
}
